DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2020.26

Domino Problem Under Horizontal Constraints

Authors: Nathalie Aubrun, Julien Esnay, and Mathieu Sablik

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract

The Domino Problem on ℤ² asks if it is possible to tile the plane with a given set of Wang tiles; it is a classical decision problem which is known to be undecidable. The purpose of this article is to parameterize this problem to explore the frontier between decidability and undecidability. To do so we fix some horizontal constraints H on the tiles and consider a new Domino Problem DP_H: given a vertical constraint, is it possible to tile the plane? We characterize the nearest-neighbor horizontal constraints where DP_H is decidable using graphs combinatorics.

Cite as

Nathalie Aubrun, Julien Esnay, and Mathieu Sablik. Domino Problem Under Horizontal Constraints. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{aubrun_et_al:LIPIcs.STACS.2020.26,
  author =	{Aubrun, Nathalie and Esnay, Julien and Sablik, Mathieu},
  title =	{{Domino Problem Under Horizontal Constraints}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{26:1--26:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.26},
  URN =		{urn:nbn:de:0030-drops-118875},
  doi =		{10.4230/LIPIcs.STACS.2020.26},
  annote =	{Keywords: Dynamical Systems, Symbolic Dynamics, Subshifts, Wang tiles, Undecidability, Domino Problem, Combinatorics, Tilings, Subshifts of Finite Type}
}

Search Results

Documents authored by Esnay, Julien

Domino Problem Under Horizontal Constraints

Abstract

Cite as

Thanks for your feedback!

Could not send message